public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] coins = new int[]{2};
        int amount = 3;
        System.out.println(test.coinChange(coins, amount));
    }

    public int coinChange(int[] coins, int amount) {
        /**
         * 零钱兑换
         * 状态表示：
         *  dp[i][j]表示使用i种硬币，恰好凑成金额j 此时最少的硬币个数
         * 状态转移方程：
         *  dp[i][j] = dp[i-1][j];
         *  if(j >= coins[i] && (j == coins[i] || dp[i-1][j - coins[i]] != 0 || dp[i][j - coins[i]] != 0)) {
         *      // 能组成的情况下，取最小值
         *      int theMin = Math.min(dp[i-1][j - coins[i]], dp[i][j - coins[i]]);
         *      int theMax = Math.max(dp[i-1][j - coins[i]], dp[i][j - coins[i]]);
         *      int theVal = theMin == 0 ? theMax + 1 : theMin + 1;
         *      if(dp[i][j] != 0) {
         *          dp[i][j] = Math.min(dp[i][j], theVal);
         *      } else {
         *          dp[i][j] = theVal;
         *      }
         *  }
         * 初始化：
         *  无需初始化
         * 填表顺序：
         *  从上到下，从左到右
         * 返回值：
         *  return 最后一列除0外最小值，若是全为0，则返回-1
         * */
        // 1 预处理
        if(amount == 0) return 0;
        int n = coins.length;
        // 2 创建dp表
        int[][] dp = new int[n+1][amount+1];
        // 3 初始化

        // 4 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= amount; j++) {
                // 不选择时直接使用前面的状态
                dp[i][j] = dp[i-1][j];
                // 若是选择，则要保证前者至少有一个状态有效，故判断：保证前者至少存在一个
                if(j >= coins[i-1] && (j == coins[i-1] || dp[i-1][j - coins[i-1]] != 0 || dp[i][j - coins[i-1]] != 0)) {
                    int theMin = Math.min(dp[i-1][j - coins[i-1]], dp[i][j - coins[i-1]]);
                    int theMax = Math.max(dp[i-1][j - coins[i-1]], dp[i][j - coins[i-1]]);
                    int theVal = theMin == 0 ? theMax + 1 : theMin + 1;
                    if(dp[i][j] != 0) {
                        // 能组成的情况下，取最小值
                        dp[i][j] = Math.min(dp[i][j], theVal);
                    } else {
                        // 不能组成的情况下，直接使用该值
                        dp[i][j] = theVal;
                    }
                }
            }
        }
        // 5 返回值
        int ret = 0x3f3f3f3f;
        for(int k = 1; k <= n; k++) {
            if(dp[k][amount] >= 1 && ret > dp[k][amount]) {
                ret = dp[k][amount];
            }
        }
        return ret == 0x3f3f3f3f ? -1 : ret;
    }
}
